import java.util.ArrayList;

public class meragSort {
    public static void mergesort(int[] arr) {
        merageChild(arr,0,arr.length-1);
    }

    private static void merageChild(int[] arr, int l, int r) {
        if(l>=r){
            return;
        }
        //分解
        int mid = l + (r - l) / 2;
        merageChild(arr,l,mid);
        merageChild(arr,mid+1,r);

        //合并
        merge(arr,l,mid,r);
    }
    private static void merge(int[] arr, int l, int mid, int r) {
        int s1=l;
        int e1=mid;
        int s2=mid+1;
        int e2=r;
        ArrayList<Integer> array=new ArrayList<>();
        while(s1<=e1 && s2<=e2) {
            if(arr[s1]<=arr[s2]) {
                array.add(arr[s1++]);
            }else{
                array.add(arr[s2++]);
            }
        }
            while(s1<=e1) {//s2走完
                array.add(arr[s1++]);
            }
            while(s2<=e2) {//s1走完
                array.add(arr[s2++]);
            }
            for(int i=0; i<array.size(); i++) {
                arr[l+i]=array.get(i);
            }

    }
    public static void mergesortNor(int[] arr) {//非递归
        int gap=1;
        while(gap<arr.length) {
            for(int i=0; i<arr.length; i=i+2*gap) {//比较完跳到下一个数组
                int left=i;
                int mid=left+gap-1;
                if(mid>=arr.length) {
                    mid=arr.length-1;
                }
                int right=mid+gap;
                if(right>=arr.length) {
                    right=arr.length-1;
                }
                merge(arr,left,mid,right);

            }
            gap*=2;
        }
    }
}
